import java.util.*;

/**
 * @author LKQ
 * @date 2022/4/1 11:08
 * @description 不用邻接链表，只用邻接矩阵表示两者是否
 */
public class Solution2 {
    public static void main(String[] args) {

    }
    public int maximalNetworkRank(int n, int[][] roads) {
        // 用来存放两城市间连接状态
        boolean[][] isConnected = new boolean[n][n];
        // 存放节点度数
        int[] in = new int[n];
        for (int[] road : roads){
            in[road[0]]++;
            in[road[1]]++;
            isConnected[road[0]][road[1]] = true;
            isConnected[road[1]][road[0]] = true;
        }
        int max = 0;
        for (int i = 0; i < n; i++){
            // 两城市不同，因此j从i+1起步
            for (int j = i + 1; j < n; j++){
                // 如果两城市相连，则需要将结果排除两城市间道路被重复计算的一次
                if (isConnected[i][j]){
                    max = Math.max(max, in[i] + in[j] - 1);
                    continue;
                }
                // 反之结果为两城市节点度数之和
                max = Math.max(max, in[i] + in[j]);
            }
        }
        return max;
    }

}
